package com.gxc.sort;

import com.gxc.randomArray.generateRandomArray;

import java.util.PriorityQueue;

/**
 * 小跟堆
 */
public class smallheap {

    public static void main(String[] args) {
        int[] arr = generateRandomArray.generateArray(20, 30);

        generateRandomArray.sout(arr);

        int k = 6;
        smallheapsort(arr, k);

        System.out.println("=======排序后=====");

        generateRandomArray.sout(arr);
    }

    private static void smallheapsort(int[] arr, int k) {
        PriorityQueue<Integer> smallheap = new PriorityQueue<>();

        int index = 0;
        for (; index<=Math.min(arr.length, k);index++) {
            smallheap.add(arr[index]);
        }

        int i = 0;
        for (;index<arr.length;index++,i++) {
            smallheap.add(arr[index]);
            arr[i] = smallheap.poll();
        }

        while (!smallheap.isEmpty()) {
            arr[i++] = smallheap.poll();
        }
    }
}
